package com.fanshuai.algorithms.datastructure.linear;

import com.fanshuai.queue.LinkedQueue;
import com.fanshuai.queue.Queue;
import com.fanshuai.stack.Stack;

/**
 * 队列实现栈
 * 使用一个队列q实现栈
 * 入栈：队列q入队，同时记录队尾元素
 * 出栈：由于需要将队尾元素弹出，因此先将队首元素不断移到队尾，然后更新队尾元素，弹出队尾元素
 * 获取栈顶元素：返回队尾元素
 */
public class QueuedStack<E> implements Stack<E> {
    private Queue<E> queue;
    private E tail;

    public QueuedStack() {
        queue = new LinkedQueue<>();
    }

    @Override
    public int size() {
        return queue.size();
    }

    @Override
    public boolean isEmpty() {
        return queue.isEmpty();
    }

    @Override
    public void push(E e) {
        queue.enqueue(e);
        tail = e;
    }

    @Override
    public E pop() {
        if (isEmpty()) {
            return null;
        }

        int size = queue.size();
        while (size > 2) {
            E data = queue.dequeue();
            queue.enqueue(data);
            size--;
        }

        E data = queue.dequeue();
        tail = data;
        queue.enqueue(data);

        return queue.dequeue();
    }

    @Override
    public E peek() {
        return tail;
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new QueuedStack<>();

        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println("top=" + stack.peek());

        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println("size=" + stack.size());

        stack.push(3);
        stack.push(4);
        stack.push(5);

        System.out.println("size=" + stack.size());
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}
